package exercise;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution8 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // 排序
        Arrays.sort(nums);

        List<List<Integer>> ans = new ArrayList<>();

        int len = nums.length;
        int cur = 0;

        // 固定第一个数
        while (cur < len-3) {
            // 固定第二个数
            int cur2 = cur+1;
            while (cur2 < len-2) {
                // 双指针
                int l = cur2 + 1, r = len - 1;
                while (l < r) {
                    long sum = (long)nums[cur] + nums[cur2] + nums[l] + nums[r];
                    // System.out.println(sum);
                    if (sum > target) {
                        r--;
                    } else if (sum < target) {
                        l++;
                    } else {
                        ans.add(new ArrayList<Integer>(
                            Arrays.asList(nums[cur], nums[cur2], nums[l], nums[r])));
                        l++; r--;
                        // 去重
                        while (l < r && nums[l] == nums[l-1]) l++;
                        while (l < r && nums[r] == nums[r+1]) r--;
                    }
                }
                cur2++;
                // 去重
                while (cur2 < len-2 && nums[cur2] == nums[cur2-1]) cur2++;
            }
            cur++;
            // 去重
            while (cur < len-3 && nums[cur] == nums[cur-1]) cur++;
        }
        return ans;
    }
}